#! /usr/bin/env python3
# coding = uft-8

# Distinct Subsequences

class Solution(object):
    def numDistinct(self, s, t):
        """
        It should be something like "how many different ways we can get the subsequence of S to become T".
        """

        a, b = t, s
        len_a, len_b = len(a), len(b)
        if len_b < len_a:
            return 0
        # T = [[0] * len_b] * len_a
        T= [[0] * len_b  for i in range(len_a)]
        # for i in range(len_a):
        #    T[i][0] = 0

        tmp = 0
        for i in range(len_b):
            if b[i] == a[0]:
                tmp += 1
            T[0][i] = tmp

        for n in range(1, len_b):
            for m in range(1, len_a):
                if m > n:
                    T[m][n] = 0
                    continue
                if b[n] == a[m]:
                    T[m][n] = T[m - 1][n - 1] + T[m][n - 1]
                else:
                    T[m][n] = T[m][n - 1]
        return T[len_a - 1][len_b - 1]

s = Solution()
print(s.numDistinct(s="", t="a"))
